6 December 1999
To: cryptography@c2.net Subject: Forthcoming Biryukov/Shamir result against A5/1 GSM privacy algorithm Date: Sun, 05 Dec 1999 22:36:28 -0500 From: Matt Blaze <mab@research.att.com> ------- Forwarded Message Date: Sun, 5 Dec 1999 15:31:21 +0200 (IST) From: Adi Shamir <shamir@wisdom.weizmann.ac.il> To: mab@research.att.com Subject: FYI Dear Matt, You may be interested in the following new result: Real-Time Cryptanalysis of GSM's A5/1 on a PC Alex Biryukov and Adi Shamir Computer Science Department The Weizmann Institute Rehovot 76100, Israel Abstract: A5/1 is the strong version of the encryption algorithm used by about 100 million GSM customers in Europe to protect the over-the-air privacy of their cellular voice and data communication. The best published attacks against it require between 2^40 and 2^45 steps. This level of security makes it vulnerable to hardware-based attacks by large organizations, but not to software-based attacks on multiple targets by hackers. In this paper we describe a new attack on A5/1, which is based on subtle flaws in the tap structure of the registers, their noninvertible clocking mechanism, and their frequent resets. The attack can find the key in less than a second on a single PC with 128 MB RAM and two 73 GB hard disks, by analysing the output of the A5/1 algorithm in the first two minutes of the conversation. The attack requires a one time parallelizable data preparation stage whose complexity can be traded-off between 2^37 and 2^48 steps. The attack was verified with an actual implementation, except for the preprocessing stage which was extensively sampled rather than completely executed. Remark: The attack is based on the unofficial description of the A5/1 algorithm at http://www.scard.org. Discrepancies between this description and the real algorithm may affect the validity or performance of our attack. I'll email you the paper in a few days, when its ready. Best wishes, Adi. ------- End of Forwarded Message
Date: Sun, 05 Dec 1999 23:29:18 -0800 From: Lucky Green <shamrock@cypherpunks.to> To: "cypherpunks@Algebra. COM" <cypherpunks@Algebra.COM> Subject: FW: cracking GSM A5/1 Executive summary: sub-second attack against A5/1. I am in communications with Shamir. The actual paper has not yet been released. -----Original Message----- From: Lucky Green [mailto:shamrock@cypherpunks.to] Sent: Sunday, December 05, 1999 20:49 To: John Gilmore Cc: cryptography@c2.net Subject: RE: cracking GSM A5/1 > Real-Time Cryptanalysis of GSM's A5/1 on a PC > > Alex Biryukov and Adi Shamir At last! Congratulations are in order. Way to go, Alex and Adi! Between the COMP128 and A5/2 work of our group and Alex and Adi's break of A5/1, my motivation for finishing that software radio-based GSM interception station has just increased greatly. Not that I wasn't motivated to begin with. :-) Even counting the almost 200 GB of drive space that seem to be required by this new attack, we still should come in well under the USD 10,000 target figure. We tested the code the came out of my reverse engineering against official test vectors, so I am confident that Alex and Adi's caveat that the attack will only work if the A5/1 code is correct won't be an issue. It will be interesting to see the actual attack. Our 15 milliseconds attack against A5/2 only works because several properties of the cipher come together just right. I wonder if the same holds true for the new attack against A5/1... We live in interesting times, --Lucky Green <shamrock@cypherpunks.to> "Among the many misdeeds of British rule in India, history will look upon the Act depriving a whole nation of arms as the blackest." - Mohandas K. Gandhi, An Autobiography, pg 446 http://www.citizensofamerica.org/missing.ram
Date: Sat, 04 Dec 1999 19:10:11 -0800 From: Lucky Green <shamrock@cypherpunks.to> Subject: RE: New Yorker article on NSA surveillance, crypto regs To: "Steven M. Bellovin" <smb@research.att.com> Cc: cryptography@c2.net Dave Emery wrote: > And much of the worlds wireless phone plant is GSM, which is > almost always encrypted, which must add significantly to NSAs burden > intercepting it, even if they can break keys very quickly... Being rather familiar with GSM crypto, allow me to say this: most GSM voice traffic globally is encrypted using A5/2. We know how to break A5/2 in five clock cycles on an ASIC. For an agency that operates interception satellites costing USD 1.5 billion each featuring antennas over twice the size of a football field, adding 5 lousy clock cycles for the cryptanalysis to the many clock cycles required to demodulate a GSM call can not be considered to be significant. Immaterial would be a better term. A5/1 likely requires more clock cycles. How many clock cycles we don't know and won't know until the cryptographic community takes a serious look at A5/1. But I from what I know about A5/1, it won't be a showstopper by any standard. I know how to build a GSM interception station using off-the-shelf hardware and a PII running Linux for a total cost of well below USD 10k. Give me a couple of billions of dollars, peanuts for the NSA, and I hereby guarantee you that I can take that system down to a single chip and some RF hardware. --Lucky Green <shamrock@cypherpunks.to> "Among the many misdeeds of British rule in India, history will look upon the Act depriving a whole nation of arms as the blackest." - Mohandas K. Gandhi, An Autobiography, pg 446 http://www.citizensofamerica.org/missing.ram
Date: Sun, 05 Dec 1999 23:03:25 -0800 From: Lucky Green <shamrock@cypherpunks.to> Subject: RE: New Yorker article on NSA surveillance, crypto regs To: die@die.com Cc: cryptography@c2.net Dave Emery wrote: > I certainly humbly defer to your expertise on the subject. I was > aware that A5/2 was very weak, though not aware that a 5 cycle result > had been found, and fully expect that (as indicated by the Shamir > announcement) that there probably is a similar very fast solution > to a5/1. And one supposes NSA has long ago derived these results in house > though some talented outsiders have yet to find a really cheap > A5/1 crack that would trivialize the required compute, meaning that > finding such is not totally trivial. Your observation that you didn't know about the 5 clock cycle attack on A5/2 is noted. Our group really needs to sit down and write our long overdue GSM crypto paper. Other than better funding, the NSA has the advantage over us "outsiders" in that the NSA or their European counterparts designed A5/1 and A5/2. They didn't have to find a compromise. They had the luxury of being able to engineer it in. Our 5 clock cycles attack against A5/2 only works because several properties of the cipher come together just right. Chance? Many doubt it. We can only wait and see if similar "fortunate coincidences" play a role in the new attack against A5/1. > As you say, we shall simply have to wait and see what kind of > crack is most effective and how low the cracking cost goes. Shamir's > recent letter hints at cracking time and resources comparable with those > required to demodulate the call and follow the protocol - or less... I am delighted that Biryukov and Shamir found a sub-second attack on A5/1. Our group had an attack of just a tad under 2^40 based on Golic's paper, but I just knew there had to be a much better attack. It didn't appear that we would find that attack. I had tried to get others interested in cryptanalyzing A5/1, but most cryptanalysts are busy working on the AES candidates. For a while there, I thought that we might have to wait until AES is chosen before A5/1 would receive some serious attention. I am glad that it didn't take that long, since some 250 million GSM users worldwide currently rely on the supposed voice privacy features of GSM. Other than perhaps DES, GSM's COMP128, A5/1, and A5/2 are by far the most widely used cryptographic algorithms in the world. [On the GSM interception station project]. > Have you actually written the code and tried it ? How well did > it work ? And in particular have you actually cracked real A5/1 even > with a 2^45 or so workfactor ? The project is still underway. It is a complex project and I don't expect it to be fully completed before 2Q2000. I am confident that the project will succeed, but I'd rather not go into more detail at this time. Watch this space. ;-) --Lucky